package com.huangyi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 三数之和
        Solution solution1 = new Solution();
        System.out.println("三数之和:");
        int[] nums1 = {-1, 0, 1, 2, -1, -4};
        System.out.println("nums = [-1,0,1,2,-1,-4]");
        System.out.println("结果: " + solution1.threeSum(nums1)); // [[-1,-1,2],[-1,0,1]]

        // 测试用例 - 四数之和
        Solution2 solution2 = new Solution2();
        System.out.println("\n四数之和:");
        int[] nums2 = {1, 0, -1, 0, -2, 2};
        System.out.println("nums = [1,0,-1,0,-2,2], target = 0");
        System.out.println("结果: " + solution2.fourSum(nums2, 0)); // [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
    }

    // 三数之和
    static class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            int n = nums.length;
            List<List<Integer>> ret = new ArrayList<>();

            for (int i = 0; i < n - 2; ) {
                // 优化：如果最小值大于0，后面不可能有和为0的三元组
                if (nums[i] > 0) {
                    break;
                }
                int left = i + 1, right = n - 1, target = -nums[i];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        ret.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        left++;
                        right--;
                        // 去重：跳过重复的left
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        // 去重：跳过重复的right
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    }
                }
                // 去重：跳过重复的i
                i++;
                while (i < n - 2 && nums[i] == nums[i - 1]) {
                    i++;
                }
            }
            return ret;
        }
    }

    // 四数之和
    static class Solution2 {
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            int n = nums.length;
            List<List<Integer>> ret = new ArrayList<>();

            // 第一层循环
            for (int i = 0; i < n - 3; ) {
                // 第二层循环
                for (int j = i + 1; j < n - 2; ) {
                    int left = j + 1, right = n - 1;
                    long aim = (long) target - nums[i] - nums[j]; // 防止溢出
                    while (left < right) {
                        int sum = nums[left] + nums[right];
                        if (sum < aim) {
                            left++;
                        } else if (sum > aim) {
                            right--;
                        } else {
                            ret.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                            left++;
                            right--;
                            // 去重
                            while (left < right && nums[left] == nums[left - 1]) {
                                left++;
                            }
                            while (left < right && nums[right] == nums[right + 1]) {
                                right--;
                            }
                        }
                    }
                    // 去重j
                    j++;
                    while (j < n - 2 && nums[j] == nums[j - 1]) {
                        j++;
                    }
                }
                // 去重i
                i++;
                while (i < n - 3 && nums[i] == nums[i - 1]) {
                    i++;
                }
            }
            return ret;
        }
    }
}